package cn.good.yan.sf.t5;

/**
 * 5 查中间节点 、 判断是否是回文链表
 *
 * @author shengren.yan
 * @create 2024-07-06
 */
public class MiddleNode {

    private int value;
    public MiddleNode next;

    public MiddleNode(int value, MiddleNode next) {
        this.value = value;
        this.next = next;
    }

    // 查中间节点 (快慢指针)
    public MiddleNode getMiddle(MiddleNode old) {
        MiddleNode p1 = old;
        MiddleNode p2 = old;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    // 判断是否是回文链表  方式1 ： 组合
    public boolean isHw1(MiddleNode old) {
        MiddleNode m = getMiddle(old);
        MiddleNode n = fz(m);
        while (n != null) {
            if (n.value != old.value) {
                return false;
            }
            n = n.next;
            old = old.next;
        }
        return true;
    }

    public MiddleNode fz(MiddleNode old) {
        MiddleNode node = null;
        while (old != null) {
            MiddleNode o2 = old.next;
            old.next = node;
            node = old;
            old = o2;
        }
        return node;
    }

    // 判断是否是回文链表  方式2 ： 优化
    public boolean isHw2(MiddleNode old) {
        MiddleNode p1 = old;  // 慢指针
        MiddleNode p2 = old;  // 快指针
        MiddleNode n = null;  // 新
        MiddleNode o = old;   // 旧
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            // 反转链表 -- p1 与 原反转 o2 相等，用p1代替
            o.next = n;
            n = o;
            o = p1;
        }
        if (p2 != null) {
            // 奇数节点
            p1 = p1.next;
        }
        n.loop();
        System.out.println("-----------");
        p1.loop();
        while (n != null) {
            if (n.value != p1.value) {
                return false;
            }
            n = n.next;
            p1 = p1.next;
        }

        return true;
    }

    public static void main(String[] args) {
        MiddleNode o5 = new MiddleNode(2, null);
        MiddleNode o4 = new MiddleNode(2, o5);
        MiddleNode o3 = new MiddleNode(3, o4);
        MiddleNode o2 = new MiddleNode(2, o3);
        MiddleNode o1 = new MiddleNode(1, o2);

        MiddleNode b4 = new MiddleNode(2, null);
        MiddleNode b3 = new MiddleNode(2, b4);
        MiddleNode b2 = new MiddleNode(2, b3);
        MiddleNode b1 = new MiddleNode(1, b2);
        System.out.println("------------");
        // 查中间节点：
//        MiddleNode r1 = o1.getMiddle(o1);
//        MiddleNode r1 = o1.getMiddle(b1);
//        r1.loop();
        // 是否是回文链表  -- 方式1
//        System.out.println(o1.isHw1(o1));
//        System.out.println(o1.isHw1(b1));
        // 是否是回文链表  -- 方式2
        System.out.println(o1.isHw2(o1));
        System.out.println(o1.isHw2(b1));


    }

    public void loop() {
        for (MiddleNode i = this; i != null; i = i.next) {
            System.out.println(i.value);
        }
    }

}
